The approaches described in this section could be pursued, but are not necessarily approaches that previously have been conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
Computers may communicate with each other through a network by sending data packets to each other. While there are numerous protocols according to which one computer may address a data packet to another computer, a protocol commonly used for this purpose is Internet Protocol (IP). Typically, a data packet that is structured according to IP (an “IP data packet”) contains a source IP address and a destination IP address. By examining a destination IP address contained in an IP data packet, a network device can determine the identity of a computer to which the IP data packet ultimately should be transmitted.
The computer that originates an IP data packet (the “originating computer”) is often not directly connected to the computer for which the IP data packet is destined (the “destination computer”). The originating computer and the destination computer often transmit IP data packets through several interconnected intermediate network devices, such as network routers. Each router maintains a routing table that contains information that the router uses to select one of potentially several directly connected network devices to which the router should forward an IP data packet. Because each such directly connected network device is connected to a router port, the router selects one of potentially several ports through which to forward the packet.
By communicating the information in their routing tables to other routers and updating their routing tables based on information received from other routers, routers can attempt to “learn” from each other the network routes, or paths, from different sources to different destinations. Routers communicate such routing table information using a routing protocol. Some examples of routing protocols are distance vector protocols, such as Routing Information Protocol (RIP), and link state protocols, such as Open Shortest Path First (OSPF) protocol. RIP is described in the Internet Engineering Task Force (IETF) Request For Comments (RFC) 1058. OSPF is described in IETF RFC 1247.
Thus, one computer may send a stream of data packets through a network route, or path, to another computer. However, depending on the nature of the information contained within the data packets, the entire stream of data packets may require transmission according to a specified minimum Quality of Service (“QoS”). A QoS may specify various requirements that are to be met when transmitting a particular stream. For example, a QoS may specify a minimum bandwidth, a maximum delay, a maximum jitter, a maximum packet loss rate, a minimum path reliability, and other requirements. Being larger and more time-critical in nature, a stream of data packets that contain real-time video information may be associated with a QoS that is more demanding than a QoS that is associated with a stream of data packets that contain portions of a low-priority, text-only e-mail message.
A stream of data packets that is associated with a specified QoS should be transmitted through a network path that satisfies the QoS requirements. A network path satisfies QoS requirements if a stream of data packets may be transmitted through that network path according to the QoS requirements. If no network path satisfies the QoS requirements, then the stream of data packets typically should not be transmitted. A path that satisfies the requirements of a particular QoS is called a “feasible path” relative to the particular QoS. Therefore, given a QoS request and a set of network paths, it is desirable to find a feasible path relative to the QoS. The process of finding a feasible path and sending a stream of data packets through the feasible path is called “QoS routing.”
Traditionally, previous QoS routing approaches have been categorized either as “source” QoS routing approaches or as “distributed” QoS routing approaches. Generally, source routing approaches involve each source, such as routers, independently collecting information about the global state of a network. This “global state information” includes information about each link in the network, such as the amount of bandwidth available on each link. Once a source has collected the network's global state information, the source determines a feasible path by performing a series of algorithmic steps using the global state information. Each source independently determines a feasible path. An example of a source QoS routing approach is described as an extension to the OSPF protocol in IETF RFC 2676.
Several significant drawbacks are inherent in source routing approaches. Because each source sends and receives messages in collecting global state information, the network may be overwhelmed by massive quantities of messages that are sent to and from many sources. The number of such messages increases with the number of sources in the network. Thus, source routing approaches suffer from an inherent scalability problem. In order to maintain relatively current global state information, each source periodically collects updated global state information. As the period between such collections is decreased, the message overhead involved in such collections grows. As the period between such collections is increased, the global state information maintained by each source becomes less current and therefore less reliable, on average.
Additionally, the algorithmic steps performed by each source in order to determine a feasible path usually are computationally intense. The resources needed to perform such steps repeatedly at an acceptable speed come at a price. Because each source independently performs such steps, the expense of each source increases when source routing approaches are used.
To avoid some of the problems inherent in source QoS routing approaches, some distributed QoS routing approaches have been proposed. Unlike source QoS routing approaches, distributed QoS routing approaches generally do not centralize the task of determining a feasible path within a single source router. Distributed QoS routing approaches therefore do not require that each router independently maintain global state information. As a result, distributed QoS routing approaches typically are associated with lower computational and message overheads than those associated with source QoS routing approaches.
K .G. Shin and C. -C. Chou provided an example of a distributed QoS routing approach in “A Distributed Route-Selection Scheme for Establishing Real-Time Channels,” IFIP Sixth Int'l Conf. On High Performance Networking (1995). This approach operates by flooding messages through all of the paths in a network. Unfortunately, such complete network flooding greatly increases message overhead, especially in large networks.
S. Chen and K. Nahrstedt provided another example of a distributed QoS routing approach in “Distributed Quality-of-Service Routing in High-Speed Networks Based on Selective Probing,” University of Illinois at Urbana-Champaign, Tech. Rep. (1998). This approach floods messages through selected links that satisfy QoS requirements. However, the links are selected without any consideration of global state information. Consequently, a significant number of links is often selected, resulting in significant message overhead. H. F. Salama, D. S. Reeves, and Y. Viniotis provided yet another example of a distributed QoS routing approach in “A Distributed Algorithm for Delay-Constrained Unicast Routing,” IEEE INFOCOM'97 (1997). This approach sends a control message from a source toward a destination in order to construct a delay-constrained path. Because this approach directs the control message without any consideration of global state information, loops may occur in the control message's path. When such a loop occurs, the control message is sent back to the node from which the control message came. Such loop removal through backtracking significantly increases message overhead.
Based on the foregoing, there is a clear need for a method of discovering a feasible path in a manner that lacks the disadvantages inherent in the QoS routing approaches discussed above. More specifically, there is a need for a method of discovering a feasible path in a manner that reduces message and computational overhead, and in a manner that avoids loops.